package cn.orange.ch07_binarytree;

import cn.orange.TreeNode;

/**
 * LC235.二叉搜索树的最近公共祖先
 */
public class LC235 {
    public TreeNode lowestCommonAncestorD(TreeNode root, TreeNode p, TreeNode q) { //迭代法
        TreeNode curr = root;
        while (curr != null) {
            if (curr.val > p.val && curr.val > q.val) {
                curr = curr.left;
            } else if (curr.val < p.val && curr.val < q.val) {
                curr = curr.right;
            } else {
                return curr;
            }
        }
        return null;
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { //递归法
        if (root == null) return null;
        if (root.val > p.val && root.val > q.val) {
            return lowestCommonAncestor(root.left, p, q);
        }
        if (root.val < p.val && root.val < q.val) {
            return lowestCommonAncestor(root.right, p, q);
        }
        return root;
    }
}
